#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

// 最长回文串
class randomConsists {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> mapping;
        bool isExist = false;
        int ans = 0;

        for (int i = 0; i < s.size(); i++)
            mapping[s[i]]++;
        for (auto& element : mapping) {
            if (element.second % 2 == 0)
                ans += element.second;
            else {
                --ans += element.second;
                isExist = true;
            }
        }

        if (isExist)
            ans++;
        return ans;
    }
};

// 最长回文子串
class maxPalindrome {
public:
    string longestPalindrome(string s) {
        string res;
        for (int i = 0; i < s.size(); i++) {
            // 以s[i]为中心的回文串
            string s1 = palindrome(s, i, i);
            // 以s[i + 1]为中心的回文串
            string s2 = palindrome(s, i, i + 1);
            res = res.size() > s1.size() ? res : s1;
            res = res.size() > s2.size() ? res : s2;
        }

        return res;
    }

    string palindrome(string s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        return s.substr(left + 1, right - left - 1);
    }
};

// 最长回文子序列
class palindromeSubsequence {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        // dpTable ==> s[i..j]的最长回文子序列长度
        int dpTable[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++)
                // j < i 肯定为0
                dpTable[i][j] = 0;
        }
        for (int i = 0; i < n; i++)
            // i = j 肯定为1
            dpTable[i][i] = 1;
        
        // 从下往上遍历，填充dpTable
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j])
                    dpTable[i][j] = dpTable[i + 1][j - 1] + 2;
                else
                    dpTable[i][j] = max(dpTable[i][j - 1], dpTable[i + 1][j]);
            }
        }

        return dpTable[0][n - 1];
    }
};